怎麼到了第24天還是好想棄賽，有夠累...
預告一下最後幾天的內容可能會稍微難一點，其中包含了實作的部分，希望我們都能堅持下去。
hackMD原稿

之前介紹不同對局類型時有提到，不管是收斂型對局或是終盤時才開始收斂的對局，都有機會將其破解，跟昨天一樣可以將這些破解的殘局事先儲存起來。

Endgame Database

Endgame Database (殘局庫)就是用來儲存殘局的結果，跟開局庫不同的地方是，開局庫儲存的只是「較好」的開局，甚至有些只是儲存各種常見的開局，而殘局庫儲存的都是「正解」。

適合的棋類

不是所有的遊戲都適合製作殘局庫，前面提到需要是收斂型對局或是終盤時開始收斂的對局，不然會過於複雜。
有時候也不一定是對局複雜度的問題，還要看遊戲的特性，比如狀態空間複雜度約 的黑白棋，跟約 的西洋棋，反而是西洋棋更適合一些，看出這兩種遊戲的區別了嗎？
沒錯！黑白棋是愈下愈多顆，而西洋棋則是愈下愈少，所以要看的不是整體複雜度而是殘局時的複雜度，適合的遊戲：西洋棋、象棋、暗棋、橋牌等。

殘局庫的類型

殘局庫根據儲存的資訊可以分為以下幾類：

• WLD (Win Loss Draw)
  只儲存盤面的結果(勝/敗/和)的殘局庫就稱為WLD殘局庫。
• DTM (Distance to Mate)
  儲存距離「將死」(遊戲結束)的步數。
• DTC (Distance to Conversion)
  將局勢轉換為其他類型殘局的步數，有點像是一個轉換法，比如發生了一些不可逆的行為時，像是吃子、暗棋的翻子、西洋棋的升變，比如下圖象棋的殘局：海底撈月(紅先)。
  
  經過數手後發生了吃子行為，會變成下圖，從本來的5子殘局變成4子殘局，獲勝的過程中會發生狀態的轉換。
  
  圖片來源
• DTC (Distance to Capture)
  電腦對局導論中的DTC是Distance to Capture，指的是吃子後最後能贏棋的距離，我在暗棋殘局庫對審局函數之改良中看到的定義為距離吃子的距離，一個DTC就有三種解釋(看了三篇論文解釋也都不太一樣...)，使用前要記得看清楚定義。

建立殘局庫的方式

Retrograde Analysis (回溯分析法) 是建殘局庫最常被使用的方法，其實就是一種暴力窮舉，只是他是反向的，從終局開始逆向推導，回溯到前一個可能將死之前的盤面，窮舉出所有可能的盤面，並計算他的結果，接著再由這些已知勝負結果的盤面往回推一手，每回推一層可能的盤面就會多非常多，比如線上西洋棋殘局庫中，最多到六子的殘局，已經有3787154440416種盤面了，上面的六子西洋棋殘局庫總容量達1153GB，而且這明顯還是壓縮過的，平均每個盤面資訊用不到3bit來儲存。

殘局庫的壓縮

以下表格擷取自Endgame Tablebase，我們可以看到每多一子的殘局，殘局庫都會變大非常多，勢必得想辦法壓縮才有辦法建得更大，而且這麼大的殘局庫你根本也沒辦法將其載入至記憶體，使用上也有很多細節需要注意。

針對不同的遊戲也有不同的壓縮策略，比如要注意循環走步，或是暗棋中考慮棋種組合等價的問題，像是除了砲以外，在暗棋中剩餘棋子都能吃掉鄰近一格比自己小的棋子，就會造成很多等價的盤面，當然還有前面一直用的老招，hash map！I'll use hash map！
這邊因為來不及寫剩下幾天要進入實作環節，就會來實作殘局庫了，到時候再來詳細解釋，Talk is cheap！一邊動手做大家會更有感覺。

結論

殘局庫的建立比起開局庫稍微複雜了些，其中有很多壓縮的知識，雖然殘局庫通常比起開局庫來得大、盤面更多，還都是正解，理論上應該也能大幅提升程式棋力才對，但其實對程式棋力影響大部分還不如開局庫，一樣要看遊戲特性，比如上面的西洋棋六子殘局，真正西洋棋比賽要吃到剩下六子以下才分出勝負的其實並不多，所以進到殘局庫的機會就比開局庫小得多，導致英雄無用武之地，相當可惜。

Reference

• 電腦對局導論
• Endgame Tablebase
• Design and implementation aspects of a Surakarta program
• Equivalence Classes in Chinese Dark Chess Endgames
• Compressing Chinese Dark Chess Endgame Databases by Deep Learning
• 線上象棋殘局庫
• 線上西洋棋殘局庫
• 暗棋殘局庫的壓縮與實做
• 象棋殘局庫之研究
• 利用深度學習技法的暗棋殘局庫壓縮及檢索研究
• 暗棋殘局庫對審局函數之改良